#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/12/11 19:54
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 高级-盛最多水的容器.py
# @Software: PyCharm
from utils.main import main, opt_list


class Solution:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        a = []
        for i in range(n):
            a.append((i, height[i]))
        a.sort(key=lambda x: x[1])

        m0 = a[n-1][0]
        m1 = a[n-1][0]
        ans = 0
        for i in range(n - 2, -1, -1):
            x = a[i]
            ans0 = x[1] * max(abs(x[0] - m0), abs(x[0] - m1))
            ans = max(ans, ans0)
            m0 = min(m0, x[0])
            m1 = max(m1, x[0])
        return ans


def opt(height):
    solve = Solution()
    print(height)
    print('ans:')
    print(solve.maxArea(height))


def opt1():
    h = [1, 8, 6, 2, 5, 4, 8, 3, 7]
    opt(h)


if __name__ == '__main__':
    opt_list.append(opt1)
    main()
